package leetcode.L22;

import java.util.ArrayList;
import java.util.List;

class Solution {
    private List<String> res = new ArrayList<>();
    public List<String> generateParenthesis(int n) {
        //生成所有可能的括号，判断其有效性
        generate(0,n,new ArrayList<>());
        return res;
    }

    public void generate(int k,int n,List<Character> characters) {//list改成builder效率更高
        if (k == (2 * n)) {
            //判断生成括号的有效性
            if (balance(n,characters)) {
                StringBuilder builder = new StringBuilder();
                characters.forEach(item->{
                    builder.append(item);
                });
                res.add(builder.toString());
            }
        } else {
            //尝试加入一个括号，可以是左或者右
            characters.add('(');
            generate(k + 1, n, characters);
            characters.remove(characters.size() - 1);
            characters.add(')');
            generate(k + 1, n, characters);
            characters.remove(characters.size() - 1);
        }
    }

    public boolean balance(int n,List<Character> characters) {
        int balance = 0;
        for (Character character : characters) {
            if (character.equals('(')) {
                balance++;
            } else {
                balance--;
            }
            if (balance<0) {
                return false;
            }
        }
        if (balance == 0) {
            return true;
        }
        return false;
    }
}